lib/Mi manual de algoritmos/version_maraton_nacional_2008/src/grafos/dijkstra.cpp

   1 #include <iostream>
   2 #include <algorithm>
   3 #include <queue>
   4
   5 using namespace std;
   6
   7 struct edge{
   8   int to, weight;
   9   edge() {}
  10   edge(int t, int w) : to(t), weight(w) {}
  11   bool operator < (const edge &that) const {
  12     return weight > that.weight;
  13   }
  14 };
  15
  16 int main(){
  17   int N, C=0;
  18   scanf("%d", &N);
  19   while (N-- && ++C){
  20     int n, m, s, t;
  21     scanf("%d %d %d %d", &n, &m, &s, &t);
  22     vector<edge> g[n];
  23     while (m--){
  24       int u, v, w;
  25       scanf("%d %d %d", &u, &v, &w);
  26       g[u].push_back(edge(v, w));
  27       g[v].push_back(edge(u, w));
  28     }
  29
  30     int d[n];
  31     for (int i=0; i<n; ++i) d[i] = INT_MAX;
  32     d[s] = 0;
  33     priority_queue<edge> q;
  34     q.push(edge(s, 0));
  35     while (q.empty() == false){
  36       int node = q.top().to;
  37       int dist = q.top().weight;
  38       q.pop();
  39
  40       if (dist > d[node]) continue;
  41       if (node == t) break;
  42
  43       for (int i=0; i<g[node].size(); ++i){
  44         int to = g[node][i].to;
  45         int w_extra = g[node][i].weight;
  46
  47         if (dist + w_extra < d[to]){
  48           d[to] = dist + w_extra;
  49           q.push(edge(to, d[to]));
  50         }
  51       }
  52     }
  53     printf("Case #%d: ", C);
  54     if (d[t] < INT_MAX) printf("%d\n", d[t]);
  55     else printf("unreachable\n");
  56   }
  57   return 0;
  58 }